package dfs;

import org.junit.Test;

import java.util.Arrays;

// 方法2(未实现): 假设数组和为sum, 添加负号的元素的和为neg, 则有: (sum-neg)-neg=target, neg=(sum-target)/2, 问题变为背包问题
public class TargetSum494 {
    @Test
    public void test() {
        findTargetSumWays(new int[]{1,1,1,1,1}, 3);
        findTargetSumWays(new int[]{1}, 1);
        findTargetSumWays(new int[]{1, 2}, 3);
    }

    // 搜索, 复杂度高
    public int findTargetSumWays(int[] nums, int target) {
        int ways = findTargetSumWaysRecusively(nums, 0, 0, target);
        System.out.format("nums: %s, target: %d, ways: %d\n", Arrays.toString(nums), target, ways);
        return ways;
    }

    public int findTargetSumWaysRecusively(int[] nums, int prevSum, int currIndex, int target) {
        if (currIndex == nums.length){
            if (prevSum == target) {
                return 1;
            } else {
                return 0;
            }
        }
        // target不要减了, prevSum已经加了, shit
        return findTargetSumWaysRecusively(nums, prevSum + nums[currIndex], currIndex+1, target) +
                findTargetSumWaysRecusively(nums, prevSum - nums[currIndex], currIndex+1, target);
    }
}
